#include <stdio.h>
#include <stdlib.h>
#include "llist.h"

#define NAMESIZE 32

struct score_st
{
    int id;
    char name[NAMESIZE];
    int math;
    int chinese;
};

struct node_st
{
    struct score_st data;
    struct node_st* l, * r;
};

void print_s(struct score_st* d)
{
    printf("%d %s %d %d\n", d->id, d->name, d->math, d->chinese);
}

int insert(struct node_st** root, struct score_st* data)
{
    struct node_st* node;

    if (*root == NULL) {
        node = malloc(sizeof(*node));
        if (node == NULL) {
            return -1;
        }

        node->data = *data;
        node->l = NULL;
        node->r = NULL;
        *root = node;
        return 0;
    }

    if (data->id <= (*root)->data.id) {
        return insert(&(*root)->l, data);
    }
    return insert(&(*root)->r, data);
}

struct score_st* find(struct node_st* root, int id)
{
    if (root == NULL) {
        return NULL;
    }

    if (id == root->data.id) {
        return &root->data;
    }

    if (id < root->data.id) {
        return find(root->l, id);
    }
    else {
        return find(root->r, id);
    }

}

void draw_(struct node_st* root, int level)
{
    if (root == NULL) {
        return;
    }

    draw_(root->r, level + 1);
    for (int i = 0; i < level; i++) {
        printf("\t");
    }
    print_s(&root->data);
    draw_(root->l, level + 1);
}

void draw(struct node_st* root)
{
    draw_(root, 0);

}

static int get_num(struct node_st* root)
{
    int num = 0;

    if (root == NULL) {
        return 0;
    }
#if 0
    if (root->l == NULL && root->r == NULL) {
        num = 1;
    }
    else {
        num += 1;
        num += get_num(root->l);
        num += get_num(root->r);
    }
    return num;
#endif

    return get_num(root->l) + 1 + get_num(root->r);
}

static struct node_st* find_min(struct node_st* root)
{
    if (root->l == NULL) {
        return root;
    }
    return find_min(root->l);
}

static struct node_st* find_max(struct node_st* root)
{
    if (root->r == NULL) {
        return root;
    }
    return find_min(root->r);
}

static void turn_left(struct node_st** root)
{
    struct node_st* node = *root;

    if (*root == NULL) {
        return;
    }
    if ((*root)->r == NULL) {
        return;
    }

    *root = node->r;
    node->r = NULL;

    find_min(*root)->l = node;
    // draw(*root);
}

static void turn_right(struct node_st** root)
{
    struct node_st* node = *root;

    if (*root == NULL) {
        return;
    }
    if ((*root)->l == NULL) {
        return;
    }

    *root = node->l;
    node->l = NULL;
    find_max(*root)->r = node;
    //draw(*root);
}

void balance(struct node_st** root)
{
    int sub;

    if (*root == NULL) {
        return;
    }


    while (1) {
        sub = get_num((*root)->l) - get_num((*root)->r);

        if (sub >= -1 && sub <= 1) {
            break;
        }
        if (sub < -1) {
            turn_left(root);
        }
        else {
            turn_right(root);
        }
    }
    balance(&(*root)->l);
    balance(&(*root)->r);

}

static void delete(struct node_st** root, int id)
{
    struct node_st** node = root;
    struct node_st *cur = NULL;

    while (*node != NULL && (*node)->data.id != id) {
        if (id < (*node)->data.id) {
            node = &(*node)->l;
        }
        else {
            node = &(*node)->r;
        }
    }

    if(*node == NULL) {
        return;
    }
    cur = *node;

    if(cur->l == NULL) {
        *node = cur->r;
    }
    else {
        *node = cur->l;
        find_max(cur->l)->r = cur->r;
    }
    free(cur);
}

#if 0
void travel(struct node_st *root)
{
    if(root == NULL) {
        return;
    }
    print_s(&root->data);
    travel(root->l);
    travel(root->r);
}
#else
void travel(struct node_st *root)
{
    queue_create();
}

#endif

int main()
{
    int arr[] = { 1,2,3,7,6,5,9,8,4 };
    int i;
    struct node_st* tree = NULL;
    struct score_st tmp, * datap;

    for (i = 0; i < sizeof(arr) / sizeof(*arr); i++)
    {
        tmp.id = arr[i];
        snprintf(tmp.name, NAMESIZE, "stu%d", arr[i]);
        tmp.math = rand() % 100;
        tmp.chinese = rand() % 100;

        insert(&tree, &tmp);
    }

    draw(tree);

    balance(&tree);

    printf("\n====================================\n");

    draw(tree);

    printf("\n====================================\n");

    travel(tree);






#if 0
    int tmpid = 5;
    delete(&tree, tmpid);

    balance(&tree);
    draw(tree);
#endif
#if 0
    int tmpid = 12;
    datap = find(tree, tmpid);
    if (datap == NULL) {
        printf("Can not find the id %d\n", tmpid);
    }
    else {
        print_s(datap);
    }
#endif
    exit(0);
}